package day2_linkedlist.leetcode;

/**
 * @Author: yuisama
 * @Date: 2021/8/31 20:51
 * @Description:删除排序链表中的重复元素 II
 * https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/
 * 存在一个按升序排列的链表，
 * 给你这个链表的头节点 head ，
 * 请你删除链表中所有存在数字重复情况的节点，只保留原始链表中没有重复出现的数字。
 * 返回同样按升序排列的结果链表。
 * 输入：head = [1,2,3,3,4,4,5]
 * 输出：[1,2,5]
 */
public class Num82 {

//    public ListNode deleteDuplicates(ListNode head) {
//        ListNode dummyHead = new ListNode(-1,head);
//        ListNode prev,cur;
//        prev = dummyHead;
//        cur = dummyHead.next;
//        while (cur != null) {
//            ListNode next = cur.next;
//            if (next == null)
//                return dummyHead.next;
//            if (cur.val != next.val) {
//                // 没有重复元素，两个指针后移一个单位
//                prev = prev.next;
//                cur = cur.next;
//            }else {
//                // 重复节点可能出现多次，用while循环
//                while (next != null && cur.val == next.val) {
//                    next = next.next;
//                }
//                prev.next = next;
//                cur = next;
//            }
//        }
//        return dummyHead.next;
//    }

    /**
     * 递归法
     * @param head
     * @return
     */
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        if (head.val != head.next.val) {
            head.next = deleteDuplicates(head.next);
            return head;
        }
        ListNode next = head.next;
        while (next != null && head.val == next.val) {
            next = next.next;
        }
        // 去重头结点后，其他的删除交给子函数
        return deleteDuplicates(next);
    }



}
